/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/palindrome-partitioning
   @Language: C++
   @Datetime: 19-09-04 16:33
   */

// Method 1, Backtrack, Time 84ms, Space 55MB
class Solution {
	bool ispalindrome(const string &s){
		for(int i=0, j=s.length()-1; i<j;)
			if (s[i++]!=s[j--]) return false;
		return true;
	}
	void backtrack(string s, vector<string> v, vector<vector<string> > &vs){
		if(s.length()==0){
			vs.push_back(v);
			return;
		}
		for(int len=1; len<=s.length(); ++len){
			string a=s.substr(0,len);
			if(ispalindrome(a)){
				v.push_back(a);
				backtrack(s.substr(len),v,vs);
				v.pop_back();
			}
		}
	}
public:
	vector<vector<string>> partition(string s) {
		vector<vector<string> > vs;
		backtrack(s,{},vs);
		return vs;
	}
};

// Method 2, Divide and Conquer with DP, Time 112ms, Space 118MB
class Solution {
	bool ispalindrome(const string &s){
		for(int i=0, j=s.length()-1; i<j;)
			if (s[i++]!=s[j--]) return false;
		return true;
	}
	vector<vector<string> > dnc(string &s, int begin, vector<vector<bool> > &dp){
		vector<vector<string> > vs;
		for(int len=1; begin+len<=s.length(); ++len){
			if(!dp[begin][begin+len-1]) continue;
			string a=s.substr(begin,len);
			if(begin+len==s.length()) vs.push_back({a});
			for(vector<string> &v:dnc(s,begin+len,dp)){
				v.insert(v.begin(),a);
				vs.push_back(v);
			}
		}
		return vs;
	}
public:
	vector<vector<string>> partition(string s) {
		int n=s.length();
		vector<vector<bool> > dp(n,vector<bool>(n,false));
		for(int len=1; len<=n; ++len)
			for(int i=0; i+len<=n; ++i){
				const int j=i+len-1;
				dp[i][j]=s[i]==s[j]&&(len<3||dp[i+1][j-1]);
			}
		return dnc(s,0,dp);
	}
};
